package com.le.tester.imooc.oldfairy.coding.sorting;

import org.junit.Test;

import java.util.Arrays;

/**
 * createTime：2023/5/24 14:06
 * description：第二种快速排序
 */
public class QuickSort1 implements IMutableSorter {
    @Override
    public void sort(int[] arr) {
        this.quickSort(arr, 0, arr.length);

        System.out.println(Arrays.toString(arr));
    }

    private void quickSort(int[] arr, int l, int r) {
        if (r - l <= 1) {
            return;
        }

        int i = partition(arr, l, r);

        quickSort(arr, l, i);
        quickSort(arr, i + 1, r);

    }

    //left mid right
    private int partition(int[] arr, int l, int r) {
        int x = arr[l];
        //使用x为一个中介，大于x的放在右边为一堆，小于x的放在左边为一堆
        int i = l + 1;
        int j = r;

        while (i != j) {
            if (arr[i] < x) {
                i++;
            } else {
                Helper.swap(arr, i, --j);
            }
        }

        Helper.swap(arr, i - 1, l);
        return i - 1;
    }


    @Test
    public void testQuickSort1() {
        this.sort(new int[]{9, 8, 8, 5656, 53, 2364, 56, 978, 9, 8});
    }
}
